// #define print(...)
#define OK(s,p) (*((s)-1)==*((p)-1) || '.'==*((p)-1))
class Solution {
public:
    bool isMatch(string s, string p) {
        auto sz = s.size();
        auto pz = p.size();
        vector< vector<bool> > dp(sz+1, vector<bool>(pz+1));
        dp[0][0] = true;
        auto st = s.begin(), pt = p.begin();
        for(int i=0; i<=sz; i++){
            for(int j=1; j<=pz; j++){
                if('*' == p[j-1]){
                    if(dp[i][j-2])
                        dp[i][j] = true;
                    else if(i && OK(st+i, pt+j-1))
                        dp[i][j] = dp[i-1][j];
                }else if( i && OK(st+i, pt+j) && dp[i-1][j-1]){
                    dp[i][j] = true;
                }
            }
        }
        return dp[sz][pz];
    }
};
